package com.hch.algorithm.leet;

import com.hch.algorithm.binarytree.ThreeNode;
import com.hch.algorithm.binarytree.TreeNode;
import org.springframework.stereotype.Component;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

@Component
public class BinaryTreeLeetBookImpl implements BinaryTreeLeetBook {

    private Map<String, Integer> memo = new ConcurrentHashMap<>();

    private List<TreeNode> treeNodes = new LinkedList<>();

    //[3,2,1,6,0,5]
    @Override
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        int maxValue = Integer.MIN_VALUE;
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                index = i;
            }
        }
        TreeNode<Integer> root = new TreeNode<>(maxValue);
        root.setLeft(constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, index)));
        root.setRight(constructMaximumBinaryTree(Arrays.copyOfRange(nums, index + 1, nums.length)));

        return root;
    }

    public static void main(String[] args) {
        int[] preorder = {1, 2, 5, 4, 6, 7, 3, 8, 9};
        int[] objects = Arrays.copyOfRange(preorder, 0, 2);
        for (int object : objects) {
            System.out.println(object);

        }
    }

    @Override
    public TreeNode<Integer> buildTree105(int[] preorder, int[] inorder) {
        return build105(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    @Override
    public TreeNode<Integer> buildTree106(int[] postorder, int[] inorder) {
        return build106(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
    }

    @Override
    public ThreeNode connect(ThreeNode root) {
        if (root == null) {
            return null;
        }
        connect(root.getLeft(), root.getRight());
        return root;
    }

    @Override
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.getLeft());
        flatten(root.getRight());
        TreeNode left = root.getLeft();
        TreeNode right = root.getRight();
        root.setLeft(null);
        root.setRight(left);
        TreeNode p = root;
        while (p.getRight() != null) {
            p = p.getRight();
        }
        p.setRight(right);
    }

    private void connect(ThreeNode left, ThreeNode right) {
        if (left == null || right == null) {
            return;
        }
        left.setNext(right);
        connect(left.getLeft(), left.getRight());
        connect(right.getLeft(), right.getRight());
        connect(left.getRight(), right.getLeft());
    }

    @Override
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return treeNodes;
    }

    // 记录结果
    int res = 0;
    // 记录当前元素的排名
    int rank = 0;

    @Override
    public int kthSmallest(TreeNode<Integer> root, int k) {
        kthSmallest(root.getLeft(), k);
        rank++;
        if (rank == k) {
            res = root.getData();
            return res;
        }
        kthSmallest(root.getRight(), k);
        return res;
    }

    int sum = 0;

    @Override
    public TreeNode<Integer> convertBST(TreeNode<Integer> root) {
        if (root == null) {
            return null;
        }
        convertBST(root.getRight());
        sum += root.getData();
        root.setData(sum);
        convertBST(root.getLeft());
        return root;
    }

    @Override
    public TreeNode<Integer> deleteNode(TreeNode<Integer> root, int key) {
        if (root == null) {
            return null;
        }
        if (root.getData() == key) {
            if (root.getRight() == null) {
                root= root.getLeft();
            } else if (root.getLeft() == null) {
                root= root.getRight();
            }else {
                TreeNode<Integer> minNode = getMinNode(root.getRight());
                root.setRight(deleteNode(root.getRight(), minNode.getData()));
                root.setData(minNode.getData());
            }
        } else if (root.getData() > key) {
            root.setLeft(deleteNode(root.getLeft(), key));
        } else if (root.getData() < key) {
            root.setRight(deleteNode(root.getRight(), key));
        }
        return root;
    }

    private TreeNode<Integer> getMinNode(TreeNode<Integer> root) {
        while (root.getLeft() != null) {
            root = root.getLeft();
        }
        return root;
    }

    private String traverse(TreeNode root) {
        if (root == null) {
            return "#";
        }
        String left = traverse(root.getLeft());
        String right = traverse(root.getRight());
        String treeOfString = root.getData() + "," + left + "," + right;
        Integer treeNum = memo.getOrDefault(treeOfString, 0);
        if (treeNum == 1) {
            treeNodes.add(root);
        }
        memo.put(treeOfString, treeNum + 1);
        return treeOfString;
    }

    private TreeNode<Integer> build106(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd) {
        if (postStart > postEnd) {
            return null;
        }
//       后序遍历最后一个元素为根点
        int rootVal = postorder[postEnd];
        TreeNode<Integer> root = new TreeNode<>(rootVal);
//        定义中序遍历根点的下标数
        int index = 0;
        for (int i = 0; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }
//        左子树的长度
        int leftSize = index - inStart;
//        构造当前节点的左子树
        root.setLeft(build106(postorder, postStart, postStart + leftSize - 1,
                inorder, inStart, index - 1));
//        构造当前节点的右子树
        root.setRight(build106(postorder, postStart + leftSize, postEnd - 1,
                inorder, index + 1, inEnd));
        return root;
    }

    private TreeNode<Integer> build105(int[] preorder, int preStart, int preEnd,
                                       int[] inorder, int inStart, int inEnd) {

        if (preStart > preEnd) {
            return null;
        }

        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // rootVal 在中序遍历数组中的索引
        int index = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        int leftSize = index - inStart;

        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构造左右子树
        root.setLeft(build105(preorder, preStart + 1, preStart + leftSize,
                inorder, inStart, index - 1));

        root.setRight(build105(preorder, preStart + leftSize + 1, preEnd,
                inorder, index + 1, inEnd));
        return root;
    }

}
